public class demo1 {
    class Solution {
        // int[]memo;
        // public int tribonacci(int n) {
        //   memo=new int[n+1];
        //   return dfs(n);
        // }
        // public int dfs(int n){
        //     if(memo[n]!=0){
        //         return memo[n];
        //     }
        //    if(n==0){
        //     memo[n]=0;
        //     return 0;
        //     }
        //    if(n==1||n==2){
        //     memo[n]=1;
        //     return 1;
        //    }
        //    memo[n]=dfs(n-1)+dfs(n-2)+dfs(n-3);
        //     return memo[n];
        // }
        public int tribonacci(int n) {
            int[]dp=new int[n+1];
            if(n==0)return 0;
            if(n==1||n==2)return 1;
            dp[1]=dp[2]=1;
            for(int i=3;i<=n;i++){
                dp[i]=dp[i-3]+dp[i-2]+dp[i-1];
            }
            return dp[n];
        }
    }
}
